1. Field of the Invention
The present invention relates to power-residue calculating units used for encryption and decryption of information applicable in the fields of telecommunications network, traffic, finance, medical services, distribution and so on. More particularly, the present invention relates to a power-residue calculating unit using a Montgomery algorithm.
2. Description of the Background Art
Owing to the technological development in the field of telecommunication, security (namely, to prevent criminal use or destruction of data) over a communication network has received a great deal of attention. Therefore, encryption and decryption of information are frequently used. The applicable fields of encryption and decryption range from telecommunication to traffic, finance, medical services, distribution and so on. This type of encryption and decryption are required to realize an advanced security based on a simple concept.
To facilitate understanding of this type of technique, a concept of encryption/decryption of information will be briefly described. In the world of encryption, “asymmetric cipher algorithm” is superior. The asymmetric cipher algorithm refers to a cipher algorithm using different encryption and description keys, where one of which cannot be “easily calculated” from the other. An RSA (Rivest-Shamir-Adleman scheme) cipher using a power-residue calculation (a residue is obtained by multiplying a certain number X several times and then dividing the result by another number N) is representative of the asymmetric cipher algorithm.
Basically, the power-residue calculation in accordance with the following formula (1) is used to generate an RSA cipher. Formula (1) means that a residue is obtained by dividing XY by N. In formula (1), X represents a plaintext to be subjected to encryption (or decryption), where Y and N are keys for encryption (or decryption).XY mod N  (1)
The power-residue calculation facilitates encryption and decryption of information. If the operand bit lengths of X, Y, and N are increased, decryption of each key becomes difficult.
However, the greater operand bit length requires a longer period of time for the power-residue calculation. Then, what is most important is how to reduce the time for the power-residue calculation with a greater operand bit length.
Next, encryption and decryption processes using the power-residue calculation will be described with an RSA cipher by way of example.
[Encryption and Decryption of RSA Cipher]
For decryption of the RSA cipher, the following equation (2) is used.C=Me mod N  (2)
For decryption, the following equation (3) is used.M=Cd mod N  (3)
Here, M represents a plaintext for encryption, and C represents a plaintext which has been subjected to encryption, i.e., a ciphertext. Further, e and N in equation (2) are encryption keys, whereas d and N in equation (3) are decryption keys. Further, the relationship as shown in the following equations (4) and (5) is assumed.N=p·q  (4)1≡e·d mod {LCM (p−1, q−1)}  (5)
Here, “≡” indicates that the left and right sides are similar to each other, and “LCM” is an abbreviation for a least common multiple. Further, p and q are relatively prime integers. Note that e and N are public keys, whereas d, p and q are secret keys.
Equations (4) and (5) both define conditions of numeric values for the power-residue calculation in a cipher algorithm. Equation (4) indicates that N is a product of relatively prime large prime numbers p and q. Since p and q are both odd numbers, N should also be an odd number. Equation (5) indicates that a residue, which is obtained by dividing a product of e and d by a least common multiple of values obtained by subtracting 1 respectively from p and q shown in equation (4), is 1.
Under the conditions specified in equations (4) and (5), plaintext M is encrypted by equation (2), and encrypted plaintext M (ciphertext C) is decrypted by equation (3).
[Method of Power-Residue Calculation]
A method of a power-residue calculation used for encryption/decryption will now be described. The power-residue calculation for A=Me mod N is carried out with use of an iterative square product method as shown in the following flow 1 with a binary digit expansion of an integer e being ek−1 . . . e1e0.
(Flow 1)beginA = 1for i = k − 1 to 0 beginA = A2 mod N...(6)If ei = 1 then A = A·M mod N...(7) endend
A solution of the power-residue calculation would be equal to A.
As described above, the calculation is based on multiplication and division (mod calculation) as shown in equations (6) and (7). The multiplication provides A×A or A×M for a value of A having an initial value of 1. The division provides mod N for a value obtained by each multiplication (a calculation of a residue when divided by N). Calculations are iteratively performed in accordance with a bit value of “e” with a pair of “multiplication and division” (A×A mod N, A×M mod N). More specifically, “multiplication and division” is performed in accordance with each bit starting from the most significant bit to the least significant bit of “e”.
As described above, in the power-residue calculation, a solution is obtained by iteratively performing basic residual calculations (mod calculation). The iterative frequency per se is at most several hundreds to several thousands of times, which can be processed by a software at high speed.
However, to carry out the residue calculation per se, i.e., division, by a hardware, a large calculation circuit and a complicated process are required, and there have been demand for an improvement. Since large integers of about 1024 bits are usually used for e, d, M, N and so on, even a high-speed exponential calculation still requires multiple precision multiplication and residual calculation of about 1500 times on average per RSA calculation. In particular, various high-speed methods, including an approximation method, residual table method and Montgomery algorithm, have been proposed for the residual calculation.
To increase the speed of the power-residue calculation mostly used for a public key cryptograph representative of the RSA cipher, the speed of one residual calculation must be increased. A Montgomery algorithm provides high speed residual calculation. In particular, in the multiplication residual calculation, division can be simplified by e.g., bit shift. Thus, the power-residue calculation used for a public key cryptograph (e.g., RSA cipher) can be performed at higher speed.
On the other hand, the Chinese remainder theorem states that a calculation modulo a composite number can be carried out by calculations modulo relatively prime factors of the composite number. If this is applied to RSA encryption with 1024-bit length, in practice, only a calculating circuit with a modulus of an integer of a 512-bit length (here corresponding to p and q), rather than a power-residue calculating circuit modulo N of a 1024-bit length, is required as hardware. This contributes to miniaturization of the hardware.
As described above, the size of the calculating circuit disadvantageously increases since the power-residue calculation involves a highly complicated process of basic residue calculation (mod calculation). Then, Montgomery has proposed that a solution can be obtained by “multiplication” and a simple bit-string process, rather than by the above described general method of residual calculation (mod calculation). The method proposed by Montgomery will be briefly described in the following.
[Montgomery Algorithm]
A Montgomery algorithm implementing high speed residual calculation will be described.
The Montgomery algorithm is based on the fact that use of residual modulus N (N>1) and a cardinal number R (R>N) which is relatively prime with respect to residual modulus N allows calculation of TR−1 mod N to be performed only by division by cardinal number R with a dividend being T. This eliminates the need for division by N for the residual calculation.
Here, N, R, R−1 and T are integers. Dividend T satisfies 0≦T<R·N. R−1 is an inverse of cardinal number R according to residual modulus N. Further, consider an integer N′ that satisfies a relation of R·R−1−N·N′=1 (0≦R−1<N, 0≦N′<R). Further, if a power of 2 is used for cardinal number R, the division by cardinal number R can be replaced by a shift operation. Thus, a high speed calculation of T→4TR−1 mod N (TR−1 mod N with a dividend being T) is enabled.
An algorithm MR (T) of T→TR−1 mod N is given below as algorithm 1. Note that in algorithm 1, (T+m·N)/R has been proved to be always divisable.
(Algorithm 1) Algorithm Y=MR (T) of T→TR−1 mod N is given by the following sequence.M=(T mod R)·N′ mod R  (8)Y=(T+m·N)/R  (9)
if Y≧N then Y=Y−N                Y<N then return Y        
A single MR provides only TR−1 mod N rather than a residue T mod N. Thus, to find residue T mod N, an MR calculation is again performed using a product of MR (T) and preliminary found R2 mod N as shown below.
                              MR          ⁡                      (                                          MR                ⁡                                  (                  T                  )                                            ·                              (                                                      R                    2                                    ⁢                  mod                  ⁢                                                                                                    ⁢                                                                                                  ⁢                  N                                )                                      )                          =                                            (                                                TR                                      -                    1                                                  ⁢                mod                ⁢                                                                                          ⁢                                                                                        ⁢                N                            )                        ·                          (                                                R                  2                                ⁢                mod                ⁢                                                                                          ⁢                                                                                        ⁢                N                            )                        ·                          R                              -                1                                              ⁢          mod          ⁢                                                            ⁢                                                          ⁢          N                                        =                                            TR                              -                1                                      ·                          R              2                        ·                          R                              -                1                                              ⁢          mod          ⁢                                                            ⁢                                                          ⁢          N                                        =                  T          ⁢                                          ⁢          mod          ⁢                                                            ⁢                                                          ⁢          N                    
Thus, residue T mod N can be found.
An algorithm implementing the multiplication residue calculation by the Montgomery method using the iterative square product method (iterative square method) of the power-residue calculation is given below. Search is performed starting from an upper bit of key e and, if the bit value of the key is 1, the Montgomery multiplication residual calculation of MR (X·Y) is performed.
Y = Rr (Rr = R2 mod N (R = 2k+2))X = MX = MR (X·Y)...(10)Y = MR (1·Y)...(11)for j = k to 1if ej == 1 then Y = MR (X·Y)...(12)if j > 1 then Y = MR (X·Y)...(13)end forY = MR (1·Y)...(14)Y = Y mod N...(15)
Here, MR (X·Y) and MR (Y·X) are equal, where ej represents j-th bit of key e. In the case of an integer with 512-bit length, k=512. The power-residue calculation of 512 bits can be implemented by the Montgomery multiplication residue calculation of 514 bits and the residual calculation of 512 bits.
The Montgomery multiplication residual calculation result P=MR (B·A) is found in the following manner by a sequential calculation of a cardinal number W which is most suitable for being implemented as hardware.
W = 2dN0′ = N′ mod WP = 0for j = 0 to kM = (P mod W) · N0′...(16)P = ((P+(A mod W)·B·W+M·N)/W)...(17)A = A/W...(18)end
Here, d is a natural number depending on the hardware. Thus, Montgomery multiplication residual calculation result P can be found. Then, 514-bit Montgomery multiplication residual calculation result P=MR (B·A) can be found in the following manner by a sequential calculation of cardinal number 2 where d=1.
N0′ = N′ mod 2P = 0for j = 0 to 514M = (P mod 2) · N0′...(19)P = ((P + (A mod 2)·B·2+M·N)/2)...(20)A = A/2...(21)end
As described above, to implement the power-residue calculation, a common practice is to use the Montgomery method for the 512-bit length power-residue calculation in the hardware and to use a process making use of the Chinese remainder theorem in the software. There are a plurality of kinds of hardware implementations, which may be employed in practice.
As conventional techniques for the RSA cipher, for example, Japanese Patent Laying-Open No. 7-20778 discloses RSA cipher, Montgomery method and a correction device, and Japanese Patent Laying-Open No. 11-212456 discloses RSA cipher and Montgomery method.
Furthermore, for example, Japanese Patent Laying-Open No. 10-269060 discloses RSA cipher, elliptical cryptography and Montgomery method.
For hardware for encryption using the algorithm described above, a so-called “Power Analysis” scheme may be used to externally search for an encryption key.
In equipment provided with ciphers such as personal computers, mobile phones and IC cards, Simple Power Analysis, Differential Power Analysis and the like are known as a scheme to observe consumed current in LSI to search for a key for encryption.
Here, the hardware for performing the encryption processing for the RSA cipher as described above desirably has a highest possible immunity against Power Analysis.
For this purpose, it is desirable that the consumed current pattern of the hardware has so fewer characteristics that the internal algorithm cannot be estimated. Moreover, it is desirable that the current pattern depending on confidential data that cannot be controlled externally does not exist. In addition, it is desirable that there is a low correlation between externally controllable input data and consumed current values and that there are fewer characteristics in the level pattern of the correlation between the externally controllable input data and the consumed current values.
In the power-reside calculation described above, the process is performed with a bit value of “e” as a unit. Therefore it is desirable that the consumed current does not vary depending on “1” or “0” of the bit value.